package com.heima.algorithm.sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * <strong>考虑了最坏情况、多重复元素、小规模数据、分区方案的最全面的快速排序</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/1 18:36
 */
public class QuickSortDuplicate {
    //（1）基于比较的排序算法
    //（2）最好情况：O(NlogN)，最坏情况：O(N^2)，平均情况：O(NlogN)，空间复杂度：O(logN)，稳定：否，思想：分而治之
    //（3）快排可能存在最坏情况，需要把枢轴值选取得尽量随机化来缓解最坏情况下的时间复杂度
    //（4）最好情况就是分区每次都很均匀，递归深度就是logN，每次分区操作需要N，所以最好O(NlogN)，最坏情况就是分区极不平衡，一边0一边剩余所有，这种递归深度就是N

    private static final int INSERTION_SORT_THRESHOLD = 32; // 插入排序的临界值

    /**
     * 快速排序
     *
     * @param arr 待排序数组
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序递归实现
     *
     * @param arr   待排序数组
     * @param begin 待排序范围的起始索引（包含）
     * @param end   待排序范围的结束索引（包含）
     */
    private static void quickSort(int[] arr, int begin, int end) {
        // 递归结束条件：当前范围内数组的个数小到一定程度用插入排序
        if (end - begin + 1 <= INSERTION_SORT_THRESHOLD){
            insertionSort(arr, begin, end);
            return;
        }
        // 递的时候将基准点元素放到合适位置并且把比基准点小的元素放基准点元素左边，比基准点大或等的元素放基准点元素右边
        int pivot = partition(arr, begin, end);
        // 再对基准点左边的区域和右边的区域进行快速排序
        quickSort(arr, begin, pivot - 1);
        quickSort(arr, pivot + 1, end);
    }

    /**
     * 洛穆托分区思想进行分区操作
     *
     * @param arr   待分区数组
     * @param begin 待分区范围的起始索引（包含）
     * @param end   待分区范围的结束索引（包含）
     * @return 分区好后的基准点元素索引
     */
    private static int partition(int[] arr, int begin, int end) {
        int le = end; // le指针负责找到小于等于基准点的元素
        int ge = begin + 1; // ge指针负责找到大于等于基准点的元素，初值设置为begin+1是因为找大于等于begin处元素的不包括它本身
        int index = ThreadLocalRandom.current().nextInt(end - begin + 1) + begin; // 随机数优化，线程安全，优化的情况是已经排好序的，不管是降序还是升序，都会有个指针每次都会走完剩下所有元素，时间复杂度回到O(N^2)
        swap(arr, index, begin); // 将随机数处的元素放到数组最左端，用随机数优化也相当于一种妥协，不用随机数的话，遇到最遭情况就会需要分n次区，而不是log n
        int pivot = arr[begin]; // 基准点元素
        while (ge <= le) { // 这里的等号不能少，最后一轮也需要处理
            // ge指针负责找到大于等于基准点的元素，不能交换，交换后arr[ge]可能先会有越界异常
            while (ge <= le && arr[ge] < pivot) { // 就是在前面找到比基准点大的交换到后面去，ge自加但是不饿能超过le
                ge++;
            }
            // le指针负责找到小于等于基准点的元素，不能交换，交换后arr[le]可能先会有越界异常
            while (ge <= le && arr[le] > pivot) { // 就是在后面找到比基准点小的交换到前面去，le自减但是不饿能小于ge
                le--;
            }
            // 当ge还是小于等于le的时候，交换两个元素
            if (ge <= le) { // 如果上一轮外层while循环退出时，ge和le指向同一个元素
                if (arr[ge] != arr[le]) {
                    swap(arr, ge, le); // 交换
                }
                ge++; // 处理下一个元素
                le--; // 处理下一个元素
            }
        }
        swap(arr, le, begin); // 将基准点元素放到合适位置，这里要用le，退出循环时，le在ge前面，前面的是小的
        return le;
    }

    /**
     * 交换两个元素
     *
     * @param arr    数组
     * @param index1 索引1
     * @param index2 索引2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    /**
     * 指定范围内进行插入排序
     * @param arr 数组
     * @param begin 指定范围内第一个元素
     * @param end 指定范围内最后一个元素
     */
    private static void insertionSort(int[] arr, int begin, int end){
        for (int i = begin + 1; i <= end; i++){
            int inserted = arr[i];
            int index = i;
            // 找到插入的位置
            while (index > begin && arr[index - 1] > inserted){
                arr[index] = arr[index - 1];
                index--;
            }
            // 插入
            if (index != i){
                arr[index] = inserted;
            }
        }
    }
}
